https://mp.weixin.qq.com/s/YdITQDsYgNV2HVlVPQFKUQ
https://juejin.cn/post/6983904373508145189
空间复杂度：执行算法需要占用多少内存空间

时间复杂度：执行当前算法所“花费的时间”




<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  
</body>
<script>
  /* 
  1、两数之和
  题目：给定一个数组 nums 和一个目标值 target，在该数组中找出和为目标值的两个数

  输入：nums: [8, 2, 6, 5, 4, 1, 3] ；target:7

  输出：[2, 5]
   */
  /* function twoNumAdd(arr, target) {
    if(Array.isArray){
      let map = {}
      for(let i = 0; i < arr.length; i++) {
        const item = arr[i]
        if(map[target - item]) {
          return [item, target - item]
        } else {
          map[item] = i
        }
      }
    }
    return []
  }
  console.log('两数之和',twoNumAdd([8, 2, 6, 5, 4, 1, 3],7)) */

  /* 题目：给定一个数组nums，判断 nums 中是否存在三个元素a，b，c，使得 a + b + c = target，找出所有满足条件且不重复的三元组合

  输入：nums: [5, 2, 1, 1, 3, 4, 6] ；target:8

  输出：[[1, 1, 6], [1, 2, 5], [1, 3, 4]] */

  /* function findThree(arr, target) {
    let result = []
    arr.sort()
    if(i && arr[i] === arr[i-1]){

    }

  } */
/* const arr = [
  { id: 1, title: "child1", parentId: 0 },
  { id: 2, title: "child2", parentId: 0 },
  { id: 3, title: "child1_1", parentId: 1 },
  { id: 4, title: "child1_2", parentId: 1 },
  { id: 5, title: "child2_1", parentId: 2 }
]
  const tranverseTree = (arr, parentId) => {
    let result = []
    for(const item of arr) {
      if(item.parentId === parentId) {
        let children = tranverseTree(arr, item.id)
        const newItem = {...item, children}
        result.push(newItem)
      }
    }
    return result
  }
  console.log('0',tranverseTree(arr,0)) */
 /*  const str = 'abcabcde'
  const firstUnReplyCod = (str) => {
    let map = {}
    for(const item of str) {
      if(map[item]){
        map[item] = map[item] + 1
      } else {
        map[item] = 1
      }
    }
    for(const key in map) {
      if(map[key] === 1){
        return str.indexOf(key)
      }
    }
  }
  console.log('23',firstUnReplyCod(str)) */

  /* 冒泡排序 */
  /* const arr = [2,4,1,9,5]
  function bubbleSort(arr) {
    //外层循环遍历到最后，内层循环遍历到arr.length - 1 - i
    for(let i = 0; i < arr.length ; i++){
      for(let j = 0; j < arr.length - 1 - i; j++) {
        if(arr[j] > arr[j+1]){
          [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        }
      }
    }
    return arr
  } */

  /* 选择排序（每次选择最小的值） */
  /* const arr = [2,4,1,9,5]
  function selectSort(arr) {
    //外层循环遍历到倒数第二个，内层循环从头遍历到尾
    //设置初始指针curMinIndex,找到最小的curMinIndex和i做交换
    for(let i = 0; i < arr.length - 1; i++){
      let curMinIndex = i
      for(j = i; j < arr.length; j++) {
        if(arr[j] < arr[curMinIndex]){
          curMinIndex = j
        }
      }
      [arr[i], arr[curMinIndex]] = [arr[curMinIndex], arr[i]]
    }
    return arr
  } */

  /* 插入排序（前面已经排好序，找到合适的位置插入进去） */
  //2,3,7,4,5  以4为列子，j依次向前寻找，4 < j的值就一直往前找，最后j找到3循环中止，把7往后移一位，3后面的值赋值给4
  /* const arr = [2,4,1,9,5]
  function inserSort(arr) {
    //假定第一个位置已经排好序，从第二个位置开始遍历
    for(let i = 1; i < arr.length; i++){
      //取出当前值
      const curValue = arr[i]
      let j = i - 1
      while(j >= 0 && curValue < arr[j]){
        arr[j+1] = arr[j]
        j--
      }
      arr[j+1] = curValue
    }
    return arr
  } */

  /* 快速排序（找到一个中间值，比它小的放到左边数组，比它大的放到右边数组，最后把三个数组整合起来,左右两个数组重新放到quickSort中递归） */
  const arr = [2,4,1,9,5,90,34,56,12]
  function quickSort(arr) {
    if(arr.length <= 1){
      return arr
    }
    const mid = Math.floor(arr.length/2)
    const base = arr.splice(mid,1)[0]
    const left = []
    const right = []
    for(const item of arr){
      if(item < base){
        left.push(item)
      } else {
        right.push(item)
      }
    }
    return [...quickSort(left),base,...quickSort(right)]
  }

  console.log('22',quickSort(arr))

  /* 归并排序 */

 </script>
</html>